//
// Created by Martin on 2022/5/8.
//

#include <iostream>
#include <random>
#include <vector>
#include <algorithm>

using namespace std;

//------------------------------------------------
// 归并排序

class MergeSort {
public:
    // 分治法 时间复杂度O(nlogn), 空间复杂度O(n)
    // 对A[left, right)进行归并排序, T是缓存空间
    static void mergeSort(vector<int> &A, int left, int right, vector<int> &T)
    {
        if (right - left > 1) {
            int m = left + (right - left) / 2;
            int p = left, q = m, i = left;

            // 递归求解
            mergeSort(A, left, m, T);  // [left, m)
            mergeSort(A, m, right, T); // [m, right)

            // 合并
            while (p < m || q < right) {
                // 第二个序列为空, 或者第一个序列非空且A[p]<=A[q]
                if (q >= right || (p < m && A[p] <= A[q])) T[i++] = A[p++];
                else T[i++] = A[q++];
            }
            // 拷贝回A数组
            for (i = left; i < right; i++) A[i] = T[i];
        }
    }

    static void merge_sort(int* A, int x, int y, int* T)
    {
        if (y-x > 1) {
            int m = x + (y-x)/2;  // 划分, 注意防止溢出
            int p = x; // 左半部[p, m]索引
            int q = m; // 右半部[m, y]索引
            int i = x; // T索引

            merge_sort(A, x, m, T); // 左半部递归求解
            merge_sort(A, m, y, T); // 右半部递归求解

            while (p < m || q < y) {
                if (q >= y || (p < m && A[p] <= A[q]))
                    T[i++] = A[p++]; // 从左半部数组复制到临时空间
                else
                    T[i++] = A[q++]; // 从右半部数组复制到临时空间
            }
            // 从辅助空间复制回A数组
            for (i = x; i < y; ++i)
                A[i] = T[i];
        }
    }
};

//------------------------------------------------
// 测试

void print_vector(vector<int>& vec) {
    cout << "{";
    for (int i = 0; i < vec.size(); ++i) {
        cout << vec[i];
        if (i < vec.size() - 1) {
            cout << ", ";
        }
    }
    cout << "}" << endl;
}

int main()
{
    // 生成Test Case
    default_random_engine e;
    uniform_int_distribution<int> u(1, 100); // 均匀分布
    constexpr int nTestCase = 50;
    vector<int> vec;
    for (size_t i = 0; i < nTestCase; ++i)
        vec.push_back(u(e));

    // 打印Test Case
    cout << "origin vector=";
    print_vector(vec);

    // 归并排序
//    vector<int> T(vec.size(), 0);
    vector<int> T;
    T.resize(vec.size());
    MergeSort::mergeSort(vec, 0, vec.size(), T);
    cout << "after merge sort, vector=";
    print_vector(vec);

    return 0;
}